package com.maltys.greedy;

import com.maltys.tree.base.TreeNode;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/binary-tree-cameras/">监控二叉树</a>
 */
public class BinaryTreeCameras {
    int cnt = 0;

    public int minCameraCover(TreeNode root) {
        if (postTraverse(root) == 0) {
            cnt++;
        }
        return cnt;
    }


    // 0 未被监控 1 有摄像头  2 被监控
    private int postTraverse(TreeNode root) {
        if (root == null) {
            return 2;
        }

        int leftState = postTraverse(root.left);
        int rightState = postTraverse(root.right);
        if (leftState == 0 || rightState == 0) {
            cnt++;
            return 1;
        }
        if (leftState == 1 || rightState == 1) {
            return 2;
        }
        if (leftState == 2 && rightState == 2) {
            return 0;
        }
        return -1;
    }
}
